package MonotoneStack.Medium;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class LC0901 {
    static class StockSpanner {
        Deque<Integer> monoStack = new ArrayDeque<>();
        ArrayList<Integer> prices = new ArrayList<>();

        public StockSpanner() {
            // 哨兵
            monoStack.push(0);
            prices.add(Integer.MAX_VALUE);
        }

        public int next(int price) {
            int idx = prices.size();
            prices.add(price);
            while (prices.get(monoStack.peek()) <= price)
                monoStack.pop();
            int top = monoStack.peek();
            monoStack.push(idx);
            return idx - top;
        }
    }

    public static void main(String[] args) {
        StockSpanner obj = new StockSpanner();
        int[] prices = new int[]{100, 80, 60, 70, 60, 75, 85};
        for (var price : prices) System.out.println(obj.next(price));
    }
}
